package leetcode.solution;

import leetcode.struct.ListNode;

/**
 * Created by tanlee on 2016/4/26.
 */
public class InsertionSortList {
    // 共定义四个指针,其中2个是目标指针和目标指针的前驱节点
    // 剩下2个是插入循环时的目标指针及其前驱节点
    public ListNode insertionSortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode tempHead = new ListNode(1);
        tempHead.next = head;
        ListNode preNode = tempHead;
        ListNode target = tempHead.next;
        ListNode tempNode = null;
        ListNode preTempNode = null;
        while (target != null) {
            tempNode = tempHead.next;
            preTempNode = tempHead;
            while (tempNode != null && tempNode != target) {
                if (tempNode.val > target.val) {
                    preNode.next = target.next;
                    preTempNode.next = target;
                    preTempNode.next.next = tempNode;
                    target = preNode;
                    break;
                } else {
                    preTempNode = preTempNode.next;
                    tempNode = tempNode.next;
                }
            }
            preNode = target;
            target = target.next;
        }
        return tempHead.next;
    }
}
